package leetcode.leetcode_1039;

import java.util.Arrays;

class Solution {
    public int minScoreTriangulation(int[] values) {
        int n = values.length;
        int[][] cache = new int[n][n];
        for (int[] row : cache) {
            Arrays.fill(row, -1);
        }
        return dfs(values, 0, n - 1, cache);
    }

    //    用dfs(i,j)为顺时针i到j的多边形的最小三角形划分和
//    dfs(i,j) = min(dfs(i,k)+dfs(k,j)+values[i]*values[j]*values[k])
//    边界条件为i== j-1 证明：i到j的边数小于3
    public int dfs(int[] values, int i, int j, int[][] cache) {
        if (i + 1 == j) return 0;
        int res = Integer.MAX_VALUE;
        if (cache[i][j] != -1) return cache[i][j];
        for (int k = i + 1; k < j; k++) {
            int temp = dfs(values, i, k, cache) + dfs(values, k, j, cache) + values[i] * values[j] * values[k];
            res = Math.min(res, temp);
        }
        return cache[i][j]= res;
    }
}